package array;

public class KMP {
  
  //http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/

  public static void main(String[] argv) {
    System.out.println ("Pattern occurs with shift " + 
        match("cbababaababaca".toCharArray(), "aaabaaa".toCharArray(),
            computePrefixFunction("aaabaaa".toCharArray())));
  }


  public static int match(char[] text, char[] pattern, int[] prefixFunc) {
    int n = text.length;
    int m = pattern.length;
    int q = 0;
    int shift = -1;
    for (int i = 0; i < n; i++) {
      while (q > 0 && pattern[q] != text[i]) {
        q = prefixFunc[q];
      }
      if (pattern[q] == text[i])
        q++;
      if (q == m) {
        shift = i - m + 1;
        break;
      }
    }
    return shift;
  }

  
  /*lps[i] = the longest proper prefix of pat[0..i] 
              which is also a suffix of pat[0..i]. 
*/
  public static int[] computePrefixFunction(char[] pattern) {
    int[] func = new int[pattern.length];
    int m = pattern.length;
    func[0] = 0;
    int k = 0;
    for (int q = 1; q < m; q++) {
      while (k > 0 && pattern[k] != pattern[q]) {
        k = func[k];
      }
      if (pattern[k] == pattern[q]) {
        k++;
      }
      func[q] = k;
    }
    return func;
  }

}